home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cpp_libs
/
answrbok
/
6_11.lha
/
6_11
/
6_11_mul.c
< prev
next >
Wrap
Text File
|
1993-08-08
|
3KB
|
126 lines
* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
* The C++ Answer Book */
* Tony Hansen */
* All rights reserved. */
*
Multiply u[1..n] * v[1..m] to form w[0..m+n]
Based on:
The Art of Computer Programming, volume 2
D. Knuth, Section 4.3.1, Algorithm M
/
include <arbint.h>
include <debug.h> /* DELETE */
rbint operator*(const arbint& tmp_u,
const arbint& tmp_v)
// Make u (the multiplicand) and
// v (the multiplier) positive.
int negu = tmp_u.isneg();
int negv = tmp_v.isneg();
arbint u(+tmp_u);
if (negu) u = -tmp_u;
arbint v(+tmp_v);
if (negv) v = -tmp_v;
f (debug&8) cerr << "operator*\n"; // DELETEdif (debug&8) outputarb(cerr, "\tu=", u.p->value, u.p->length, u.p->refcnt); // DELETE
f (debug&8) outputarb(cerr, "\tv=", v.p->value, v.p->length, v.p->refcnt); // DELETE
// The product will be negative if
// the signs of the multiplier and
// multiplicand do not match.
int negans = (negu != negv);
int n = u.p->length;
int m = v.p->length;
int wlen = n + m + 1;
ARB_type *wv = new ARB_type[wlen];
ARB_type *uv = u.p->value;
ARB_type *vv = v.p->value;
/*
M1(a) [Initialize]
Set w[m+1..m+n] <- 0
*/
memset((char*)wv, 0, wlen * sizeof(ARB_type));
f (debug&8) { outputarb(cerr, "\twv=", wv, wlen); // DELETE
err << "\tn=" << n << ", m=" << m << ", wlen=" << wlen << "\n"; } // DELETE
/*
M1(b) [Initialize]
Set j <- m
M6 [Loop on j]
decrease j by one
if j > 0, goto M2
*/
for (int j = m - 1; j >= 0; j-- )
{
/*
M2 [zero multiplier?]
if v[j] == 0
w[j] <- 0
goto M6
*/
f (debug&8)/*DELETE*/ cerr << "\tj=" << j << "\n";
f (debug&8)/*DELETE*/ cerr << "\tvv[" << j << "]=" << form("%4.4x", vv[j]) << "\n";d if (vv[j] == 0)
{d
bug&8)/*DELETE*/ cerr << "\tsetting wv[" << j << "] <- 0\n";
wv[j] = 0;
continue;
}
/*
M3 [Initialize i]
set i <- n,
k <- 0
M5(a) [Loop on i]
decrease i by one
if i > 0, goto M4
*/
ARB_Ltype v_j = vv[j];
ARB_Ltype k = 0;
for (int i = n - 1, iplusj = i + j + 2;
i >= 0;
i--, iplusj--)
{
f (debug&8)/*DELETE*/ cerr << "\ti=" << i << "\n";dif (debug&8)/*DELETE*/ cerr << "\tuv[" << i << "]=" << form("%4.4x", uv[i]) << "\n";
f (debug&8)/*DELETE*/ cerr << "\twv[" << iplusj << "]=" << form("%4.4x", wv[iplusj]) << "\n";
f (debug&8)/*DELETE*/ cerr << "\tk=" << k << "\n";d /*
M4 [multiply and add]
set t <- u[i] * v[j] +
w[i+j] + k
w[i+j] <- t % b
k <- t / b
*/
ARB_Ltype t = uv[i] * v_j +
wv[iplusj] + k;
wv[iplusj] = t; // % ARB_base;
k = t / ARB_base;
}
bug&8)/*DELETE*/ cerr << "\tend of loop on i\n";
f (debug&8)/*DELETE*/ cerr << "\tk=" << k << "\n";
f (debug&8)/*DELETE*/ cerr << "\twv[" << (j+1) << "]<-" << form("%4.4x", k) << "\n";d /*
M5(b) [Loop on i]
if i <= 0,
set w[j] <- k
*/
wv[j+1] = k;
}
/* Normalize */
f (debug&8)/*DELETE*/ cerr << "\tend of loop on j\n";
f (debug&8) outputarb(cerr, "\tw=", wv, wlen); // DELETE
arbint w(wv, wlen);
f (debug&8) outputarb(cerr, "\tw=", w.p->value, w.p->length, w.p->refcnt); // DELETEdif (debug&8) outputarb(cerr, "\tu=", u.p->value, u.p->length, u.p->refcnt); // DELETE
f (debug&8) outputarb(cerr, "\tv=", v.p->value, v.p->length, v.p->refcnt); // DELETE
/* Restore sign and return */
if (negans)
return -w;
elsR
return w;